import java.util.*;

/**
 * An object that maps keys to values. A map cannot contain duplicate keys; 
 * each key can map to at most one value.
 * 
 * This implementation is based on an extendible hash map that's available
 * on Wikipedia. This version differs in that it actually implements
 * java.util.Map.
 * 
 * Also used:
 *   ACM Transactions on Database Systems (TODS)
 *   Volume 4 ,  Issue 3  (September 1979)
 *   Pages: 315 - 344  
 *   Year of Publication: 1979
 *   ISSN:0362-5915 
 * 
 * Extendible hashing is a type of hash system which treats a hash as a bit 
 * string, and uses a trie for bucket lookup. Because of the hierarchical 
 * nature of the system, re-hashing is an incremental operation (done one 
 * bucket at a time, as needed). This means that time-sensitive applications 
 * are less affected by table growth than by standard full-table rehashes.
 * 
 * @author Michael Cotterell
 * @see http://en.wikipedia.org/wiki/Extendible_hashing#Java_example
 * @see http://portal.acm.org/citation.cfm?doid=320083.320092
 * 
 * @param <K> Key type
 * @param <V> Value type
 */
public class ExtendibleHashMap<K, V> implements Map<K, V> {
	
	/**
	 * A bucket used in an ExtendibleHashMap.
	 * 
	 * @author Michael Cotterell
	 * @see http://en.wikipedia.org/wiki/Extendible_hashing#Java_example
	 *
	 * @param <K> Key type
	 * @param <V> Value type
	 */
	static class ExtendibleHashMapBucket<K, V> {
		
		/**
		 * The maximum allowed capacity of the bucket
		 */
		static int maxSize = 67108864 >> 4;
		
		/**
		 * Used for identifying the bucket
		 */
		public int id = 0;
		
		/**
		 * Map used to store the contents of the bucket.
		 */
		public Map<K, V> map = new HashMap<K,V>(maxSize);
	
		/**
		 * Returns true if this bucket contains no key-value mappings.
		 * @return a boolean indicating if this bucket contains no key-value mappings.
		 */
		public boolean isEmpty() {
			return this.map.isEmpty(); 
		}
		
		/**
		 * Returns true if this bucket has exceeded maxSize.
		 * @return a boolean indicating if this bucket has exceeded maxSize.
		 */
		public boolean isFull() {
			return (this.map.size() > maxSize);
		}
		
		/**
		 * Associates the specified value with the specified key in this bucket.
		 * @param k key
		 * @param v value
		 */
		public void put(K k, V v) {
			this.map.put(k, v);
		}
 
		/**
		 * Returns the value to which the specified key is mapped, or null if 
		 * this bucket contains no mapping for the key.
		 * @param k key
		 * @return value to which the specified key is mapped, or null if this bucket contains no mapping for the key.
		 */
		public V get(K k) {
			return this.map.get(k);
		}
		
		/**
		 * Returns the number of key-value mappings in this bucket.
		 * @return number of key-value mappings in this bucket
		 */
		public int size() {
			return this.map.size();
		}
		
	}
	
	/**
	 * Used for identifying buckets
	 */
	private int id = 0;
	
	/**
	 * List of buckets
	 */
	private List<ExtendibleHashMapBucket<K, V>> buckets = new ArrayList<ExtendibleHashMapBucket<K, V>>();
	
	/**
	 * A set of the keys in the Map. Used to implement the keySet() method.
	 */
	private Set<K> keySet = new HashSet<K>(ExtendibleHashMapBucket.maxSize);
	
	/**
	 * Constructs a new ExtendibleHashMap
	 */
	public ExtendibleHashMap() {
		/**
		 * Start by adding one bucket to Map
		 */
		this.buckets.add(new ExtendibleHashMapBucket<K, V>());
	}
	
	@Override
	public void clear() {
		this.keySet.clear();
		this.buckets.clear();
	}

	/**
	 * Retrieves the bucket that contains a mapping for the specified key.
	 * @param k key
	 * @return the buckets that holds the key.
	 */
	private ExtendibleHashMapBucket<K, V> getBucket(K k) {
		return buckets.get(k.hashCode() & ((1 << this.id) - 1));
	}
	
	@Override
	public boolean containsKey(Object arg0) {
		return (this.get(arg0) != null);
	}

	@Override
	public boolean containsValue(Object arg0) {
		for (ExtendibleHashMapBucket<K, V> bucket : this.buckets) {
			if (bucket.map.containsValue(arg0)) {
				return true;
			}
		}
		return false;
	}

	@Override
	public Set<Entry<K, V>> entrySet() {
		Set<Entry<K, V>> set = new HashSet<Entry<K, V>>();
		for (ExtendibleHashMapBucket<K, V> bucket : this.buckets) {
			set.addAll(bucket.map.entrySet());
		}
		return set;
	}

	@SuppressWarnings("unchecked")
	@Override
	public V get(Object arg0) {
		return getBucket((K) arg0).get((K) arg0);
	}

	@Override
	public boolean isEmpty() {
		return (this.size() == 0);
	}

	@Override
	public Set<K> keySet() {
		return this.keySet;
	}

	@Override
	public V put(K arg0, V arg1) {
		
		/**
		 * Grab the bucket that contains the mapping for the key
		 */
		ExtendibleHashMapBucket<K, V> bucket = getBucket(arg0);
		
		/**
		 * Add or split buckets as needed.
		 */
		if (bucket.isFull() && bucket.id == this.id) {
			
			List<ExtendibleHashMapBucket<K, V>> buckets2 = new ArrayList<ExtendibleHashMapBucket<K, V>>(this.buckets);
			this.buckets.addAll(buckets2);
			this.id++;
		
		} else if (bucket.isFull() && bucket.id < this.id) {
			
			bucket.put(arg0, arg1);
			ExtendibleHashMapBucket<K, V> bucket1 = new ExtendibleHashMapBucket<K, V>();
			ExtendibleHashMapBucket<K, V> bucket2 = new ExtendibleHashMapBucket<K, V>();
		
			for (Entry<K, V> entry : bucket.map.entrySet()) {
				K varg0 = entry.getKey();
				V varg1 = entry.getValue();
				
				int hashCode = bucket.hashCode() & ((1 << this.id) - 1);
				 
				if (((hashCode >> bucket.id) & 1) == 1) {
					bucket2.put(varg0, varg1);
				} else {
					bucket1.put(varg0, varg1);
				}
				
			}
			
			for (int i = 0; i < this.buckets.size(); ++i) {
				if (this.buckets.get(i) == bucket) {
					if (((i >> bucket.id) & 1) == 1) {
						this.buckets.set(i, bucket2);
					} else {
						this.buckets.set(i, bucket1);
					}
				}
			}
			
			bucket2.id = bucket1.id = bucket.id + 1;
			
		} else {
			bucket.put(arg0, arg1);
		}
		
		/**
		 * Add the key to the keyset
		 */
		this.keySet.add(arg0);
		
		return arg1;
	}

	@Override
	public void putAll(Map<? extends K, ? extends V> arg0) {
		for (K o : arg0.keySet()) {
			this.put(o, arg0.get(o));
		}
	}

	@Override
	public V remove(Object arg0) {
		for (ExtendibleHashMapBucket<K, V> bucket : this.buckets) {
			bucket.map.remove(arg0);
		}
		this.keySet.remove(arg0);
		return null;
	}

	@Override
	public int size() {
		int sum = 0;
		for (ExtendibleHashMapBucket<K, V> bucket : this.buckets) {
			sum += bucket.size();
		}
		return sum;
	}

	@Override
	public Collection<V> values() {
		Collection<V> collection = new HashSet<V>();
		for (ExtendibleHashMapBucket<K, V> bucket : this.buckets) {
			collection.addAll(bucket.map.values());
		}
		return collection;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		ExtendibleHashMap.testRun(1000000);
		
	}

	public static double testN = 0;
	public static List<String> testStringSet = new ArrayList<String>();
	public static List<Integer> testIntegerSet = new ArrayList<Integer>();
	
	public static Map<Integer, String> hashMap = new HashMap<Integer, String>();
	public static Map<Integer, String> treeMap = new TreeMap<Integer, String>();
	public static Map<Integer, String> extMap = new ExtendibleHashMap<Integer, String>();

	public static void generateTestSets(int n) {
		
		ExtendibleHashMap.testN = n;
		
		ExtendibleHashMap.testStringSet.clear();
		ExtendibleHashMap.testIntegerSet.clear();
		
		Random r = new Random();
		
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			ExtendibleHashMap.testIntegerSet.add(r.nextInt());
			ExtendibleHashMap.testStringSet.add("" + i);
		}
		
	}
	
	public static double testInsertHashMap() {
		
		long startA = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			ExtendibleHashMap.hashMap.put(ExtendibleHashMap.testIntegerSet.get(i), ExtendibleHashMap.testStringSet.get(i));
		}
		long stopA = System.currentTimeMillis();
		long timeA = stopA - startA;
		
		long startB = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			Integer int1 = ExtendibleHashMap.testIntegerSet.get(i);
			String str1 = ExtendibleHashMap.testStringSet.get(i);
		}
		long stopB = System.currentTimeMillis();
		long timeB = stopB - startB;
		
		return (timeA - timeB);

	}
	
	public static double testInsertTreeMap() {
		
		long startA = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			ExtendibleHashMap.treeMap.put(ExtendibleHashMap.testIntegerSet.get(i), ExtendibleHashMap.testStringSet.get(i));
		}
		long stopA = System.currentTimeMillis();
		long timeA = stopA - startA;
		
		long startB = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			Integer int1 = ExtendibleHashMap.testIntegerSet.get(i);
			String str1 = ExtendibleHashMap.testStringSet.get(i);
		}
		long stopB = System.currentTimeMillis();
		long timeB = stopB - startB;
		
		return (timeA - timeB);

	}
	
	public static double testInsertExtMap() {
	
		long startA = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			ExtendibleHashMap.extMap.put(ExtendibleHashMap.testIntegerSet.get(i), ExtendibleHashMap.testStringSet.get(i));
		}
		long stopA = System.currentTimeMillis();
		long timeA = stopA - startA;
		
		long startB = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			Integer int1 = ExtendibleHashMap.testIntegerSet.get(i);
			String str1 = ExtendibleHashMap.testStringSet.get(i);
		}
		long stopB = System.currentTimeMillis();
		long timeB = stopB - startB;
		
		return (timeA - timeB);
		
	}
	
public static double testReadHashMap() {
		
		long startA = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			String s = ExtendibleHashMap.hashMap.get(ExtendibleHashMap.testIntegerSet.get(i));
		}
		long stopA = System.currentTimeMillis();
		long timeA = stopA - startA;
		
		long startB = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			Integer int1 = ExtendibleHashMap.testIntegerSet.get(i);
		}
		long stopB = System.currentTimeMillis();
		long timeB = stopB - startB;
		
		return (timeA - timeB);
		
	}
	
	public static double testReadTreeMap() {
		
		long startA = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			String s = ExtendibleHashMap.treeMap.get(ExtendibleHashMap.testIntegerSet.get(i));
		}
		long stopA = System.currentTimeMillis();
		long timeA = stopA - startA;
		
		long startB = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			Integer int1 = ExtendibleHashMap.testIntegerSet.get(i);
		}
		long stopB = System.currentTimeMillis();
		long timeB = stopB - startB;
		
		return (timeA - timeB);
		
	}
	
	public static double testReadExtMap() {
		
		long startA = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			String s = ExtendibleHashMap.extMap.get(ExtendibleHashMap.testIntegerSet.get(i));
		}
		long stopA = System.currentTimeMillis();
		long timeA = stopA - startA;
		
		long startB = System.currentTimeMillis();
		for (int i = 0; i < ExtendibleHashMap.testN; i++) {
			Integer int1 = ExtendibleHashMap.testIntegerSet.get(i);
		}
		long stopB = System.currentTimeMillis();
		long timeB = stopB - startB;
		
		return (timeA - timeB);
		
	}
	
	public static void testRun(int n) {
		
		ExtendibleHashMap.generateTestSets(n);
		
		double insertTime = 0;
		double readTime = 0;
		double hashReadAvg = 0;
		double treeReadAvg = 0;
		double extReadAvg = 0;
		
		System.out.println("Running tests...");
		
		System.out.println();
		
		System.out.println("HashMap");
		insertTime = ExtendibleHashMap.testInsertHashMap();
		readTime = ExtendibleHashMap.testReadHashMap();
		System.out.println("Insert time         : " + insertTime + " ms");
		System.out.println("Average insert time : " + (insertTime / ExtendibleHashMap.testN) + " ms");
		System.out.println("Read time           : " + readTime + " ms");
		System.out.println("Average read time   : " + (readTime / ExtendibleHashMap.testN) + " ms");
		hashReadAvg = (readTime / ExtendibleHashMap.testN);
		
		System.out.println();
		
		System.out.println("TreeMap");
		insertTime = ExtendibleHashMap.testInsertTreeMap();
		readTime = ExtendibleHashMap.testReadTreeMap();
		System.out.println("Insert time         : " + insertTime + " ms");
		System.out.println("Average insert time : " + (insertTime / ExtendibleHashMap.testN) + " ms");
		System.out.println("Read time           : " + readTime + " ms");
		System.out.println("Average read time   : " + (readTime / ExtendibleHashMap.testN) + " ms");
		treeReadAvg = (readTime / ExtendibleHashMap.testN);
		
		System.out.println();
		
		System.out.println("ExtendibleHashMap");
		insertTime = ExtendibleHashMap.testInsertExtMap();
		readTime = ExtendibleHashMap.testReadExtMap();
		System.out.println("Insert time         : " + insertTime + " ms");
		System.out.println("Average insert time : " + (insertTime / ExtendibleHashMap.testN) + " ms");
		System.out.println("Read time           : " + readTime + " ms");
		System.out.println("Average read time   : " + (readTime / ExtendibleHashMap.testN) + " ms");
		extReadAvg = (readTime / ExtendibleHashMap.testN);
		
		System.out.println();
		
		System.out.println("Average read time for ExtendibleHashMap is " + (hashReadAvg / extReadAvg) + " times faster than HashMap.");
		System.out.println("Average read time for ExtendibleHashMap is " + (treeReadAvg / extReadAvg) + " times faster than TreeMap.");
		
	}
	
}
